Asymmetric (or public) key cryptosystems use two different keys that are not feasibly derivable from one another, one for encryption and another for decryption. A person wishing to receive messages, generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, since only he has the private key. Asymmetric-key cryptosystems may also be used to provide for digital signatures, in which the sender encrypts a signature message using his private key. Because the signature message can only be decrypted with the sender's public key, the recipient can use the sender's public key to confirm that the signature message originated with the sender. One of the best-known asymmetric-key cryptosystems is the RSA, named for its originators Rivest, Shamir and Adleman. One version of RSA is defined by ANSI Standard X9.31-1998.
RSA is widely used in many cryptographic systems. RSA gets its security from the difficulty of factoring large prime numbers. The RSA public and private keys are derived from two randomly selected large prime numbers.
The general way to derive the two RSA keys is as follows. First choose two random large prime numbers p and q. Compute N=p×q, which is referred to as the public modulus. Then randomly choose the public key e such that e and (p−1)×(q−1) are relatively prime. Finally, compute the private key d such that d=e−1mod((p−1)×(q−1)). RSA encryption and decryption formulas are straightforward. To encrypt a message m, compute c=me mod N, where c is the ciphertext. To decrypt c, compute m=cd mod N.
It has been suggested that two users with different moduli might have a common prime factor in their moduli, either by accident or because of a poor design (design flaw) in the system. If N1=p1×q1 and N2=p2×q2, where p1=p2, then it is easy to find p1 or p2 given N1 and N2, i.e., an efficient algorithm exists to find the common factor p1 or p2 given N1 and N2. If such a common prime factor were to exist, and this fact were discovered, then it would also be an easy matter to factor each modulus into its prime factors. This, of course, would allow the private keys to be computed from the corresponding public keys, and hence for the security of the keys to be compromised.
One of the drawbacks of the existing methods for RSA key generation is that six seed values may need to be stored in case an audit will be performed. These seeds will demonstrate that the primes were indeed generated at random and that the user was not trying to choose the primes with some peculiar properties. Such saving of seed values may result in a security exposure as the seed values could be illicitly obtained and used to generate the RSA key values. In commonly assigned United States Patent Application entitled “METHOD, SYSTEM AND APPARATUS FOR GENERATING SELF-VALIDATING PRIME NUMBERS” filed Jul. 10, 1998, Ser. No. 09/114,024, the disclosure of which is incorporated herein by reference, a scheme was developed that incorporated the knowledge of the seeds into the primes themselves. Therefore, the seeds need not be stored in order to pass an audit. However, the generated primes were not necessarily unique and could not be associated with a particular user.
In general, mechanisms for differentiating between users are known. For example, a particular individual can be identified or verified through a user identifier (such as a globally unique name) or biometric data (such as fingerprint, hand geometry, iris pattern, facial features, voice characteristics, handwriting dynamics, earlobe characteristics, etc.).
As is well known to those having skill in the art, biometric information is one or more behavioral and/or physiological characteristics of an individual. Biometric identification and/or verification uses a data processing system to enable automatic identification and/or verification of identity by computer assessment of a biometric characteristic. In biometric verification, biometric information is verified for a known individual. In biometric identification, biometric information for an individual is compared to known biometric information for many individuals in order to identify the individual.
Biometric identification/verification systems, methods and computer program products can measure one or more of the following behavioral and/or physiological characteristics of an individual: fingerprint, hand geometry, iris pattern, facial features, voice characteristics, handwriting dynamics, earlobe characteristics and keystroke dynamics. Other biometric characteristics may be used. Applications using biometric technologies include biometric check cashing machines, payment systems that substitute biometric data for personal identification numbers, access control systems that use biometric data, biometric employee time and attendance recording and biometric passenger control for transportation. Many other applications may utilize biometric information for identification and/or verification. See the publications entitled “Biometrics, Is it a Viable Proposition for Identity Authentication and Access Control”, to Kim, Computers & Security, Vol. 14, 1995, pp. 205-214; “A Robust Speaker Verification Biometric”, to George et al., Proceedings, the IEEE 29th International Carnahan Conference on Security Technology, Oct. 1995, pp. 41-46; “On Enabling Secure Applications Through Off-line Biometric Identification”, to Davida et al., Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy, 1998, pp. 148-157; and “Biometric Encryption: Information Privacy in a Networked World”, to Brown et al., EDI Forum: The Journal of Electronic Commerce, v. 10, No. 3, 1997, pp. 37-43. However, while biometric identification and user identification may allow for identification of users, these existing uses may not allow for authentication of the source of encryption keys.
In the above cited Davida et al. publication, in Section 5.2, it was proposed that biometrics could be used with or as keys. However, Davida et al. assumes that the biometric information is secret information. Furthermore, Davida et al. may not work for any size key and describes a procedure which may not allow for pre-computing information for generation of a key value. Furthermore, the proposal of Davida et al. may allow two users to generate the same key values and, thus, does not assure that the generated keys are disjoint.
In light of the above discussion, a need exists for improvements in the generation of encryption keys for RSA cryptosystems so as to allow authentication of user's generated values without requiring storage of the secret seed values.